/* 面试题 04.06. 后继者 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
/* 中序遍历 */
var inorderSuccessor = function (root, p) {
	const stack = []
	let prev = null,
		cur = root
	while (stack.length || cur) {
		while (cur) {
			stack.push(cur)
			cur = cur.left
		}
		cur = stack.pop()
		if (prev === p) return cur

		prev = cur
		cur = cur.right
	}
	return null
}

/* 利用二叉搜搜树的性质 */
var inorderSuccessor = function (root, p) {
	let successor = null
	/* 
        如果节点p的右子树不为空,则节点p 的后继节点在其右子树中
        在其右子树中定位到最左边的节点,即为 p的后继节点
    */
	if (p.right) {
		successor = p.right
		while (successor.left) {
			successor = successor.left
		}
		return successor
	}
	let node = root
	while (node) {
		if (node.val > p.val) {
			successor = node
			node = node.left
		} else {
			node = node.right
		}
	}
	return successor
}
